请你求解这棵树中每个结点的价值和(由于答案可能会很大,请你对998244353取模),即。
完全二叉树:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第 k 层所有的结点都连续集中在最左边。
例如(图为一棵标准的完全二叉树):
2
5
5
38
其计算公式为:1 * 1 + (2 + 3) * 2 + (4 + 5) * 3 = 38 (此式乘号前面为结点编号的和,后面为这些节点对应的深度)
数据满足:
import bisect class Solution: def tree4(self , n ): # write code here # 获取最大层数 two = [1] for i in range(30): two.append(two[-1] * 2) pre = [0] for i in range(len(two)): pre.append(pre[-1] + two[i]) pos = bisect.bisect_right(pre,n) height = pos - 1 left = n - pre[pos - 1] mod = 998244353 cnt = 1 cur = 1 ans = 0 while cnt <= height: ans += cnt * ((cur + cur + two[cnt - 1] - 1) * two[cnt - 1] // 2) % mod cur += two[cnt - 1] cnt += 1 if left: ans += pos * ((two[height] + two[height] + left - 1) * left // 2) % mod return ans % mod